package com.yequan.leetcode.dp.coinChange_322;

/**
 * //给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
 * // -1。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * // 输入: coins = [1, 2, 5], amount = 11
 * //输出: 3
 * //解释: 11 = 5 + 5 + 1
 * //
 * // 示例 2:
 * //
 * // 输入: coins = [2], amount = 3
 * //输出: -1
 * //
 * //
 * //
 * // 说明:
 * //你可以认为每种硬币的数量是无限的。
 * // Related Topics 动态规划
 *
 * @author : Administrator
 * @date : 2020/4/19
 */
public class CoinChange {

    /**
     * 动态规划
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange1(int[] coins, int amount) {
        return 0;
    }

    /**
     * 递归
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange2(int[] coins, int amount) {
        if (null == coins || coins.length == 0) {
            return -1;
        }
        int[] cache = new int[amount];
        return helper(coins, amount, cache);
    }

    private int helper(int[] coins, int amount, int[] cache) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        if (cache[amount - 1] != 0) {
            return cache[amount - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = helper(coins, amount - coin, cache);
            if (res >= 0 && res < min) {
                min = res + 1;
            }
        }
        cache[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
        return cache[amount - 1];
    }

}
